package leetcode_500;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;

/**
 *@author 周杨
 *SortCharactersByFrequency_451 将一个字符串统计其字符出现多次的放在前面 
 *describe:用TreeSet实现 AC 28%
 *2018年8月22日 下午3:24:49
 */
public class SortCharactersByFrequency_451 {
	
	public static void main(String[] args) {
		SortCharactersByFrequency_451 test=new SortCharactersByFrequency_451();
		System.out.println(test.frequencySort("tree"));
		System.out.println(test.frequencySort("aaaccbdd2ddd"));
	}

	public String frequencySort(String s) {
        Set<String> set=new TreeSet<String>(new Comparator<String>() {

			@Override
			public int compare(String o1, String o2) {
				if(o1.length()>o2.length())
					return -1;
				return 1;
			}
		});
        Map<Character,Integer> map=new HashMap<Character,Integer>();
        char[] chars=s.toCharArray();
        for(char c:chars) {
        	Integer now=map.get(c);
        	if(now==null) {
        		map.put(c, 1);
        	}
        	else
        		map.put(c, now+1);
        }
        for(Character c:map.keySet()) {
        	int count=map.get(c);
        	StringBuilder sb=new StringBuilder();
        	for(int i=0;i<count;++i) {
        		sb.append(c);
        	}
        	set.add(sb.toString());
        }
        StringBuilder sb=new StringBuilder();
        for(String str:set) {
        	sb.append(str);
        }
        return sb.toString();
    }
	
	
	/**
	 * describe:用hash  但是每次要遍历完256个字符映射 AC 80%
	 * 2018年8月22日 下午3:26:26
	 */
	public String frequencySort1(String s) {
        int[] freq = new int[256];
        char[] array = s.toCharArray();
        for (char c : array) {
            freq[c]++;
        }
        int max = 0;
        int i = 0;
        while (i < array.length) {
            for (int j = 0; j < 256; j++) {
                if (freq[j] > freq[max]) {
                    max = j;
                }
            }
            for (int k = 0; k < freq[max]; k++) {
                array[i++] = (char) max;
            }
            freq[max] = 0;
        }
        return new String(array);
    }
}
